home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / topsort.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  918b  |  67 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_edit.h>
  3.  
  4.  
  5. bool TOPSORT(const graph& G, node_array<int>& ord)
  6. { 
  7.   node_array<int> cur_indeg(G);
  8.  
  9.   list<node> zero_indeg;
  10.  
  11.   int count = 0;
  12.  
  13.   node v,w;
  14.  
  15.   forall_nodes(v,G) 
  16.   { cur_indeg[v] = G.indeg(v);
  17.     if (G.indeg(v)==0) 
  18.        zero_indeg.append(v); 
  19.    }
  20.  
  21.   while ( ! zero_indeg.empty() )
  22.   { 
  23.     count++;
  24.  
  25.     v = zero_indeg.pop();
  26.   
  27.     ord[v] = count;
  28.  
  29.     forall_adj_nodes(w,v) 
  30.        if (--cur_indeg[w]==0) zero_indeg.append(w);
  31.    }
  32.   
  33.   return (count==G.number_of_nodes());
  34. }
  35.      
  36.  
  37.  
  38.  
  39.  
  40. main()
  41. {
  42.   GRAPH<point,int>  G;
  43.  
  44.   window W;
  45.  
  46.   for(;;)
  47.   { 
  48.     graph_edit(W,G);
  49.  
  50.     node_array<int> node_num(G);
  51.  
  52.     if (TOPSORT(G,node_num)==false)
  53.     { W.acknowledge("Graph is cyclic, cannot sort");
  54.       continue;
  55.      }
  56.  
  57.     node v;
  58.     forall_nodes(v,G)
  59.        W.draw_int_node(G[v],node_num[v],blue);
  60.  
  61.    if (W.read_mouse() == 3) break;
  62.  
  63.   }
  64.  
  65.   return 0;
  66. }
  67.